package com.aug_leo.datastructure.linkedlist;

/**
 * 判断回文链表
 */
public class E09Leetcode234 {

    /*
        步骤1: 找中间点
        步骤2: 中间点后半个链表反转
        步骤3: 反转后链表与原始链表逐一比较
        1   2   3   1
        1   3

        1   2   3   2   1
        1   2   3
     */

    /*
        步骤1: 找中间点的同时反转前半个链表
        步骤2: 反转后的前半个链表 与 中间点开始的后半个链表 逐一比较

                p1      p2
        1   2   2   1   null

        n1
        2   1   2   1   null
     */
    public boolean isPalindrome(ListNode head) {
        ListNode pointer1 = head; // 慢指针
        ListNode pointer2 = head; // 快指针
        ListNode n1 = null; // 新头
        ListNode o1 = head; // 旧头
        while (pointer2 != null && pointer2.next != null) {
            pointer1 = pointer1.next;
            pointer2 = pointer2.next.next;

            // 反转链表
//            ListNode o2 = o1.next;
            o1.next = n1;
            n1 = o1;
            o1 = pointer1;
        }

        System.out.println(n1);
        System.out.println(pointer1);

        if (pointer2 != null){ // 奇数节点
            pointer1 = pointer1.next;
        }

        while (n1 != null){
            if (n1.val != pointer1.val){
                return false;
            }
            n1 = n1.next;
            pointer1 = pointer1.next;
        }
        return true;

    }

    // 反转链表
    private ListNode reverse(ListNode o1) {
        ListNode n1 = null;
        while (o1 != null) {
            ListNode o2 = o1.next;
            o1.next = n1;
            n1 = o1;
            o1 = o2;
        }

        return n1;
    }

    // 找到中间节点
    private ListNode middle(ListNode head) {
        ListNode pointer1 = head; // 慢指针
        ListNode pointer2 = head; // 快指针
        while (pointer2 != null && pointer2.next != null) {
            pointer1 = pointer1.next;
            pointer2 = pointer2.next.next;
        }
        return pointer1;
    }

    public static void main(String[] args) {
        System.out.println(new E09Leetcode234()
                .isPalindrome(ListNode.of(1, 2, 2, 1)));

        System.out.println(new E09Leetcode234()
                .isPalindrome(ListNode.of(1, 2, 3, 2, 1)));
    }
}
